# coding: utf-8

import sys
sys.path.append('../3_data_structure')
from stack import Stack


def infix_to_postfix(expression):
    op_stack = Stack()
    postfix = []

    precedence = {'**': 4, '*': 3, '/': 3, '+': 2, '-': 2, '(': 1}

    items = expression.split(' ')
    for item in items:
        if item in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ' or item in '01234567879':
            postfix.append(item)

        elif item == '(':
            op_stack.push(item)

        elif item == ')':
            top = op_stack.pop()
            while top != '(':
                postfix.append(top)
                top = op_stack.pop()

        else:
            while (not op_stack.is_empty()) and precedence[op_stack.peek()] >= precedence[item]:
                postfix.append(op_stack.pop())

            op_stack.push(item)

    while not op_stack.is_empty():
        postfix.append(op_stack.pop())

    return ' '.join(postfix)


expression = 'A * B + C * D'
print('Expect: A B * C D * +')
print('Real  : ' + infix_to_postfix(expression))

print('')

expression = 'A * ( B + C ) * D'
print('Expect: A B C + * D *')
print('Real  : ' + infix_to_postfix(expression))

print('')

expression = 'A * ( B + C )'
print('Expect: A B C + *')
print('Real  : ' + infix_to_postfix(expression))


print('')

expression = '5 * 3 ** ( 4 - 2 )'
print('Expect: 5 3 4 2 - ** *')
print('Real  : ' + infix_to_postfix(expression))
